import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//用栈实现队列
class MyQueue{
    private Stack<Integer> in;
    private Stack<Integer> out;

    public MyQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }

    //到数据
    //out空了才能到数据，in每次到需全部倒完
    public void inToOut(){
        if(out.isEmpty()) {
            while(!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

    //入队列
    public void push(int x) {
        in.push(x);
        inToOut();
    }

    //出队列
    public int pop() {
        inToOut();
        return out.pop();
    }

    //返回队列头元素
    public int peek(){
        return out.peek();
    }

    //判断是否为空
    public boolean isEmpty() {
        return in.isEmpty() && out.isEmpty();
    }
}


//用队列实现栈
class MyStack {
    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    //入栈
    public void push(int x) {
        queue.offer(x);
        int len = queue.size();
        while (len-- != 0){
            queue.offer(queue.poll());
        }
    }
    //出栈
    public int pull() {
        return queue.poll();
    }

    public int peek() {
        return queue.peek();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

}

public class ConvertStackAndQueue {
    public static void main(String[] args) {
        //创建队列
        MyQueue myQueue = new MyQueue();
        myQueue.push(9);
        myQueue.push(1);
        myQueue.push(1);
        while (!myQueue.isEmpty()) {
            System.out.print(myQueue.pop() + " ");
        }
        System.out.println();
        //创建栈
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        while(!myStack.isEmpty()) {
            System.out.print(myStack.pull() + " ");
        }
    }
}
